#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;

class Solution {
public:
    int maxSubArray(vector<int>& nums) {
        if (nums.empty()) {  // 特判：输入为空数组
            return 0;
        }
        
        int n = nums.size();  // 数组长度
        int cur_sum = nums[0];  // 当前连续子数组的和，初始化为第一个元素
        int max_sum = nums[0];  // 连续子数组和的最大值，初始化为第一个元素
        
        int start = 0;  // 最大子数组的起始下标
        int end = 0;    // 最大子数组的结束下标
        int cur_start = 0;  // 当前连续子数组的起始下标
        
        for (int i = 1; i < n; ++i) {  // 从第二个元素开始遍历
            if (nums[i] > cur_sum + nums[i]) {  // 如果当前元素比当前连续子数组的和加上当前元素更大
                cur_start = i;  // 则当前元素开始构成一个新的连续子数组，将当前元素的下标赋值给cur_start
            }
            cur_sum = max(nums[i], cur_sum + nums[i]);  // 计算当前位置的连续子数组和
            if (cur_sum > max_sum) {  // 如果当前连续子数组的和比之前的最大子数组和更大
                max_sum = cur_sum;  // 更新最大子数组和的值
                start = cur_start;  // 更新最大子数组的起始下标
                end = i;  // 更新最大子数组的结束下标
            }
        }
        
        // 输出最大子数组的元素
        cout << "[";
        for (int i = start; i <= end; ++i) {
            cout << nums[i];
            if (i < end) {
                cout << ", ";
            }
        }
        cout << "]" << endl;
        
        return max_sum;  // 返回最大子数组和
    }
};

int main()
{
    Solution s;
    vector<int> nums = {-2,1,-3,4,-1,2,1,-5,4}; //[4,-1,2,1] 的和最大，为 6 。
    cout << s.maxSubArray(nums) << endl;
    return 0;
}